{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8b239d94",
   "metadata": {},
   "source": [
    "## 动态规划\n",
    "\n",
    "### 旅程路径最短，只能向下或者向右移动\n",
    "\n",
    "```\n",
    "0 3 2 9 \n",
    "2 1 3 4 \n",
    "5 2 6 7 \n",
    "6 8 4 3\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e6badbd5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "# n, n*n matrix\n",
    "from typing import List\n",
    "\n",
    "def planPath(n:int,mat:List[List[int]])->int:\n",
    "    stateLst = [[0]*n for _ in range(n)]\n",
    "    # initialize\n",
    "    stateLst[0][0] = 0\n",
    "    for i in range(1,n):\n",
    "        stateLst[i][0] = stateLst[i-1][0] + mat[i][0]\n",
    "    for j in range(1,n): # column\n",
    "        stateLst[0][j] = stateLst[0][j-1] + mat[0][j]\n",
    "    # fill stateLst\n",
    "    for i in range(1,n):\n",
    "        for j in range(1,n):\n",
    "            stateLst[i][j] = mat[i][j] + min(stateLst[i-1][j], stateLst[i][j-1])\n",
    "    return stateLst[-1][-1]\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    # n = int(input())\n",
    "    # mat = []\n",
    "    # for i in range(n):\n",
    "    #     rowTmp = list(map(int, input().split()))\n",
    "    #     mat.append(rowTmp)\n",
    "    n = 4\n",
    "    mat = [[0,3,2,9],[2,1,3,4],[5,2,6,7],[6,8,4,3]]\n",
    "    print(planPath(n,mat))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a7dcb28",
   "metadata": {},
   "source": [
    "### 钢条切割, 利益最大化\n",
    "\n",
    "|长度| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |\n",
    "|:---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|---:|\n",
    "|价格| 1 | 5 | 8 | 9 | 10| 17| 17| 20| 24| 30 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6bb37fd8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## dp[i]: 表示长度为i的钢条的最大切割收益\n",
    "## 动态规划，记录每个长度的最大收益，避免重复计算\n",
    "def cutsteel(n: int, prices: List[int]) -> int:\n",
    "    valueLst = [0]*(n+1)  # 保存每个长度对应的最大收益\n",
    "    valueLst[1] = prices[0]\n",
    "    for j in range(1,n+1):\n",
    "        q = -float('inf')\n",
    "        for i in range(0,j):\n",
    "            q = max(q, prices[i]+valueLst[j-1-i])\n",
    "        valueLst[j] = q\n",
    "    # print(valueLst)\n",
    "    return valueLst[-1]\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # n = int(input())\n",
    "    # prices = list(map(int,input().split()))\n",
    "    n = 10\n",
    "    prices = [1,5,8,9,10,17,17,20,24,30]\n",
    "    print(cutsteel(n,prices))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82ffcebd",
   "metadata": {},
   "source": [
    "### 矩阵链乘\n",
    "> 问题描述参见  P210--\\《算法导论\\》\n",
    "> $A_1 A_2 A_3 A_4$, 矩阵序列的不同相乘顺序，对应的计算复杂度是不同的；**求复杂度最小的相乘顺序**\n",
    "\n",
    ">$size(A_1)=(p_0,p_1), size(A_2)=(p_1,p_2)$,  两者相乘的复杂度=$p_0 \\times p_1 \\times p_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "880332df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min calculated amount:15125\n",
      "((A1(A2A3))((A4A5)A6))"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 矩阵链乘问题\n",
    "# 求效率最高的全括号化方案\n",
    "# (A1*A2)*A3 的计算量为p0*p2*p1+p0*P3*p2,\n",
    "# 效率最高：计算量最小\n",
    "## mats = ['A1','A2','A3','A4','A5']\n",
    "## matszs =[[p0,p1], [p1,p2], [p2,p3], [p3,p4], [p4,p5]]\n",
    "## Ps = [p0,p1,...,p5]\n",
    "\n",
    "'''\n",
    "动态规划：\n",
    "思路： 一个完全括弧化的方案 可以看作为两个完全括弧化方案相乘\n",
    "dp[i][j]: Ai->Aj 的最小矩阵连乘计算量; Ai->Aj: 表示Ai到Aj组成的矩阵相乘链\n",
    "state[i][j]: 存储当前完全括弧化方案的分为两个方案的最佳分割点， \n",
    "    这个主要用于定位最新计算量对于的矩阵链乘方案\n",
    "\n",
    "i<=k<j, k为分割点\n",
    "dp[i][k]= 1 if i==k\n",
    "A_{i->k} * A_{k+1->j} 对于的计算量: p[i-1]*p[j]*p[k] \n",
    "dp[k+1][j] = 1 if j-1=k\n",
    "\n",
    "dp[i][j] = min_{j<=k<j}(dp[i][k]+dp[k+1][j]+q[i-1]q[j]q[k])\n",
    "state[i][j] = k # k 是最小化dp[i][j]的分割点\n",
    "'''\n",
    "\n",
    "\n",
    "def matrixMultiplyChain(Ps: List[int]) -> None:\n",
    "    L = len(Ps)-1  # 矩阵的个数\n",
    "    if L == 1:\n",
    "        return 0\n",
    "\n",
    "    dp = [[0]*(L+1) for i in range(L+1)]\n",
    "    # dp[1][L] 就是最小计算量\n",
    "    state = [[0]*(L+1) for i in range(L+1)]  # 存储 最佳分割位点\n",
    "    # 考虑短的矩阵链乘，能够被更长的矩阵链乘复用，因此采用自下而上的方案计算，复用dp[i][j]\n",
    "\n",
    "    # initialize\n",
    "    for i in range(1, L+1):\n",
    "        dp[i][i] = 1\n",
    "\n",
    "    # 使用递归求解\n",
    "    def recursion(left: int, right: int) -> None:\n",
    "        nonlocal Ps, dp, state\n",
    "        minVal = float('inf')\n",
    "        for k in range(left, right):\n",
    "            if k == left:  # A_{i->k}  只有一个矩阵\n",
    "                leftM = 0\n",
    "            else:\n",
    "                leftM = dp[left][k]  # 复用更短的完全括弧化方案\n",
    "            if k == right-1:  # A_{k+1->j}  只有一个矩阵\n",
    "                rightM = 0\n",
    "            else:\n",
    "                rightM = dp[k+1][right]\n",
    "            tmp = leftM + rightM + Ps[left-1]*Ps[right]*Ps[k]\n",
    "            if tmp < minVal:  # 只记录计算量最小的方案\n",
    "                minVal = tmp\n",
    "                dp[left][right] = minVal\n",
    "                state[left][right] = k  # 记录当前计算量对于的分割点\n",
    "\n",
    "    for l in range(2, L+1):\n",
    "        for i in range(1, (L+1-l)+1):\n",
    "            left = i\n",
    "            right = i+l-1\n",
    "            recursion(left, right)\n",
    "\n",
    "    # 最小的计算量，dp[1][L]\n",
    "    print('min calculated amount:{}'.format(dp[1][L]))\n",
    "\n",
    "    # 输出计算量最小的完全括弧话方案\n",
    "    def myPrint(left: int, right: int) -> None:\n",
    "        nonlocal state\n",
    "        if left == right:\n",
    "            print('A{}'.format(left), end='')\n",
    "            return\n",
    "        else:\n",
    "            k = state[left][right]\n",
    "            print('(', end='')\n",
    "            myPrint(left, k)\n",
    "            myPrint(k+1, right)\n",
    "            print(')', end='')\n",
    "\n",
    "    myPrint(1, L)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    ## 30*35, 35*15, 15*5, 5*10, 10*20, 20*25\n",
    "    Ps = [30, 35, 15, 5, 10, 20, 25]\n",
    "    matrixMultiplyChain(Ps)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6b3d28c",
   "metadata": {},
   "source": [
    "### 计算莱文斯坦距离（字符串的编辑距离）\n",
    "\n",
    "> 参考例题：[72. 编辑距离 - 力扣（LeetCode）](https://leetcode.cn/problems/edit-distance/)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "d799d6ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## 使用动态规划\n",
    "# 定义状态：给定字符串，A，B， DP[i][j] 表示将字符串A[:i] 转变为B[:j]所需的最小操作数\n",
    "# 三个动作会发生状态转移\n",
    "# 1. 在A的末尾删除一个字母： DP[i-1][j]+1->DP[i][j]： 删除A[i]\n",
    "# 2. 在A的末尾插入一个字母： DP[i][j-1]+1->DP[i][j],  插入B[j] 在A的末尾\n",
    "# 3. 替换A的末尾字母： DP[i-1][j-1]+1->DP[i][j] or DP[i-1][j-1]->DP[i][j], 此时需要比较A[i],B[j],相同不用操作，否则替换A[i]为B[j]\n",
    "# 绘制状态转移矩阵\n",
    "\n",
    "## 计算不同字符串的莱文斯坦距离，把a转换为b的最小操作次数（增加，删除，替换）\n",
    "## 状态转移过程\n",
    "# if a[i] ==b[j]:\n",
    "#   a:  add:(a[i],b[j+1]) remove:(a[i+1],b[j]) replace:(a[i+1],b[j+1])\n",
    "#   b:  add:(a[i+1],b[j]) remove:(a[i],b[j+1]) replace:(a[i+1],b[j+1])   \n",
    "# else:\n",
    "#   (a[i+1],b[j+1])\n",
    "# dp[i][j] 表示a[:i]和b[:j]的莱温斯坦距离\n",
    "# if a[i]==b[j]:\n",
    "#   dp[i][j] = min(dp[i-1][j-1],dp[i][j-1]+1,dp[i-1][j])\n",
    "# else:\n",
    "#   dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j-1]+1, dp[i-1][j]+1)\n",
    "# \n",
    "def calcLevenshteinDistance(a:str,b:str)->int:\n",
    "    n,m = len(a),len(b)\n",
    "    dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "    dp[0][0] = 0\n",
    "    for i in range(m+1):\n",
    "        dp[0][i] = i\n",
    "    for i in range(n+1):\n",
    "        dp[i][0] = i\n",
    "    \n",
    "    for i in range(1,n+1):\n",
    "        for j in range(1,m+1):\n",
    "            if a[i-1]==b[j-1]:\n",
    "                dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1)\n",
    "            else:\n",
    "                dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)\n",
    "\n",
    "    return dp[n][m]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    print(calcLevenshteinDistance('horse','ros'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af1d59f0",
   "metadata": {},
   "source": [
    "### 最长公共子序列数目\n",
    "\n",
    "> 参考例题：\n",
    "> [公共子串_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac)\n",
    "> [剑指 Offer II 095. 最长公共子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/qJnOS7/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d8d43955",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "## 返回公共字串长度\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## 最大公共字序列\n",
    "# dp[i][j] 表示a[:i] 和 b[:j]的最大公共字序列数目\n",
    "# if a[i]==b[j]:\n",
    "#   dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)\n",
    "# else: \n",
    "#   dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n,m = len(text1),len(text2)\n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "\n",
    "        # for i in range(m+1):\n",
    "        #     dp[0][i] = 0\n",
    "        # for i in range(n+1):\n",
    "        #     dp[i][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if text1[i-1]==text2[j-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "        return dp[n][m]\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.longestCommonSubsequence('abcde','ace'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb9a0598",
   "metadata": {},
   "source": [
    "### 最长公共字符序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "84f0ca70",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ace\n"
     ]
    }
   ],
   "source": [
    "## 返回公共子序列\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "# 最大公共字序列\n",
    "# dp[i][j] 表示a[:i] 和 b[:j]的最大公共字序列数目\n",
    "# if a[i]==b[j]:\n",
    "#   dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)\n",
    "# else:\n",
    "#   dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n, m = len(text1), len(text2)\n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "\n",
    "        # for i in range(m+1):\n",
    "        #     dp[0][i] = 0\n",
    "        # for i in range(n+1):\n",
    "        #     dp[i][0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\n",
    "        # return dp[n][m]\n",
    "        pre = dp[n][0]\n",
    "        res = []\n",
    "        for i in range(1, m+1):\n",
    "            if dp[n][i] > pre:\n",
    "                res.append(text2[i-1])\n",
    "            pre = dp[n][i]\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.longestCommonSubsequence('abcde', 'ace'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dec7617b",
   "metadata": {},
   "source": [
    "### 最长公共字符串\n",
    "\n",
    "> 参考例题：\n",
    "> [公共子串_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "1059d67f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2345\n"
     ]
    }
   ],
   "source": [
    "## 返回公共字串\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## 最大公共字串\n",
    "## 与最长公共子序列不同，字串需要连续\n",
    "## dp[i][j]: a[:i] 和b[:j]的最大公共字串\n",
    "# if a[i]==b[j]:\n",
    "#   dp[i][j] = dp[i-1][j-1]+1\n",
    "# else:\n",
    "#   dp[i][j] = 0\n",
    "class Solution:\n",
    "    def LCS(self , str1: str, str2: str) -> str:\n",
    "        # write code here\n",
    "        n,m = len(str1), len(str2)\n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "        maxval = 0\n",
    "        ipos = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if str1[i-1]==str2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                    if maxval<dp[i][j]:\n",
    "                        maxval = dp[i][j]\n",
    "                        ipos = i-1\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        # num\n",
    "        if maxval==0:\n",
    "            return ''\n",
    "   \n",
    "        return str1[ipos-maxval+1:ipos+1]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.LCS('1AB2345CD','12345EF'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a41575c7",
   "metadata": {},
   "source": [
    "### 0-1 背包问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "81a93e5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## dp[i]: 容量为i的背包能容纳的物品重量\n",
    "\n",
    "def dp_01package(capacity:int, weights:List[int])->int:\n",
    "    dp = [0]*(capacity +1)\n",
    "\n",
    "    dp[0] = 1\n",
    "    for weight in weights:\n",
    "        for i in range(capacity-weight,-1,-1): # 必须进行倒序处理，避免当前操作影响下一次\n",
    "            if dp[i]==1:\n",
    "                dp[weight+i] = 1\n",
    "    i = capacity\n",
    "    while i>=0 and dp[i]==0:\n",
    "        i-=1\n",
    "    print(dp)\n",
    "    return i\n",
    "\n",
    "if __name__=='__main__':\n",
    "    print(dp_01package(12,[2,3,2,3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc77ce1a",
   "metadata": {},
   "source": [
    "### 0-1 背包问题升级版"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6716f023",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, -1, 4, 6, 8, 10, 12, 14, 15, 18]\n",
      "18\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "# 01背包问题，物品具有价值\n",
    "## dp[i]: 容量为i的背包能容纳的最大价值\n",
    "\n",
    "\n",
    "def packageV2(capacity: int, weights: List[int], value: List[int]) -> int:\n",
    "    n = len(weights)\n",
    "    dp = [-1]*(capacity+1)  # dp[i] 容量i对应的最大价值\n",
    "    dp[0] = 0\n",
    "    for j, weight in enumerate(weights):\n",
    "        for i in range(capacity-weight, -1, -1):\n",
    "            if dp[i] != -1:\n",
    "                dp[i+weight] = max(dp[i]+value[j], dp[i+weight])\n",
    "    print(dp)\n",
    "    return max(dp)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(packageV2(9, [2, 2, 4, 6, 3], [3, 4, 8, 9, 6]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec9cc2b2",
   "metadata": {},
   "source": [
    "### 淘宝凑单问题\n",
    "> 满W的最小金额；\n",
    "> 物品列表values = \\[24,56,78,98,45,84\\]\n",
    "> W = 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1607711a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min value:201\n",
      "45 100 56 \n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "# 淘宝凑单问题\n",
    "# 物品的价值 values：\n",
    "# 物品的个数： n\n",
    "# 满减金额 W\n",
    "\n",
    "# dp[i]: 到第i个物品时被点亮的价格状态，size(dp)=(n+1,W*3+1),列表示价值集合，\n",
    "# dp[i][j] 表示遍历到第i个物品的时候，是否有可能总价格为j\n",
    "# if dp[i-1][j]:\n",
    "#   dp[i][j] = 1\n",
    "#   dp[i][j+value[i-1]] = 1\n",
    "## dp[i][j+value[i-1]] = 1\n",
    "\n",
    "\n",
    "def coudan(values: List[int], W: int) -> List[int]:\n",
    "    n = len(values)\n",
    "    dp = [[0]*(W*3+1) for _ in range(n+1)]\n",
    "\n",
    "    # initial\n",
    "    dp[0][0] = 1\n",
    "\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(W*3+1):\n",
    "            if dp[i-1][j]:\n",
    "                # 不购买当前物品\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                # 购买当前物品\n",
    "                if j+values[i-1] <= W*3:\n",
    "                    dp[i][j+values[i-1]] = 1\n",
    "\n",
    "    j = W\n",
    "    while j <= 3*W and dp[n][j] == 0:  # 从W开始找大于其的第一个值\n",
    "        j += 1\n",
    "    if j == 3*W+1:\n",
    "        return  # 没有找到\n",
    "\n",
    "    print('min value:{}'.format(j))\n",
    "    for i in range(n, 0, -1):\n",
    "        if j-values[i-1] >= 0 and dp[i-1][j-values[i-1]]:  # 只打印购买的商品价格\n",
    "            print(values[i-1], end=' ')\n",
    "            j = j-values[i-1]\n",
    "    print()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    W = 200\n",
    "    values = [4, 43, 56, 89, 100, 21, 45]\n",
    "    coudan(values, W)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02d5ea06",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
